package problem1162;

//1162.地图分析
//https://leetcode.cn/problems/as-far-from-land-as-possible/

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int maxDistance(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int ret = -1;
        boolean[][] st = new boolean[n][m];
        Queue<int[]> queue = new LinkedList<>();
        for(int i = 0; i<n; i++) {
            for(int j = 0; j<m; j++) {
                if(grid[i][j] == 1) {
                    queue.add(new int[]{i,j});
                }
            }
        }
        if(queue.size() == 0 || queue.size() == n*m) return -1;
        int[] xx = {1,-1,0,0};
        int[] yy = {0,0,1,-1};
        while(!queue.isEmpty()) {
            int size = queue.size();
            ret++;
            while(size -- > 0) {
                int[] t = queue.poll();
                int x = t[0], y = t[1];
                for(int i = 0; i<4; i++) {
                    int dx = x + xx[i];
                    int dy = y + yy[i];
                    if(dx >= 0 && dx < n && dy >= 0 && dy < m && grid[dx][dy] == 0 && !st[dx][dy]) {
                        st[dx][dy] = true;
                        queue.add(new int[]{dx, dy});
                    }
                }
            }
        }
        return ret;
    }
}